The use and decoding of one-dimensional bar codes are well known and such decoding may be accomplished relatively simply. Various forms of two-dimensional (2-D) bar codes are also known. One form of 2-D bar code designated PDF417 is described in detail in the "PDF417 Specification" authored by the present inventor, which was published in 1991. The encoding and decoding of 2-D bar codes in formats such as PDF417 are addressed at length in U.S. Pat. No. 5,243,655, granted to the present inventor on Sep. 7, 1993. As a result of the availability of these and other documents, persons skilled in this field have a relatively high level of information regarding both the encoding and decoding of 2-D bar codes. An improved form of 2-D bar code, the packet bar code, and the encoding and decoding thereof are disclosed in the present inventor's pending U.S. patent application Ser. No. 08/280,490, filed Jul. 26, 1994, the content of which is hereby incorporated by reference herein.
Typically, a 2-D bar code includes, in one form or another, a plurality of bar/space patterns, each of which represents an encoded value or data character. For example, in the application referenced above each such bar/space pattern comprises a packet consisting of a 16, 4, 5 bar code. That form of identification is representative of a group of 4 bars and 4 spaces, beginning with a bar, that is a total of 16 modules wide, with each bar and space not exceeding a width of 5 modules. FIG. 1 shows an example of such a bar code which includes 4 bars respectively 4, 2, 1 and 2 modules wide and four spaces respectively 3, 2, 1 and 1 module wide. For this purpose, a "module" is a minimum unit of width.
The FIG. 1 bar/space pattern may be considered by use of different approaches. For example, an X-sequence approach considers the sequence of bar and space widths, resulting in a 4, 3, 2, 2, 1, 1, 2, 1 sequence for the FIG. 1 pattern. A different approach is to consider widths on the basis of edge to similar edge, which has been found more reliable in some circumstances. This approach provides a T-sequence based on pattern widths between similar edges (i.e., from the start of a bar to the start of the next bar and from the start of a space to the start of the next space). On this basis, the T-sequence for the FIG. 1 bar/space pattern is 7, 5, 4, 3, 2, 3, 3. The bar code coding is desirably arranged so that the T-sequence is unique for each four bar and four space pattern utilized.
A table such as shown in FIG. 2 could be used to decode a bar/space pattern. However, a code such as the packet code referred to above utilizes different bar/space patterns providing 1024 different T-sequences to represent a like number of decoded values (e.g., decoded values 0 through 1023). A decoder using the FIG. 2 table would thus have to make comparisons for up to 1024 table positions in order to either find a match identifying the decoded value or a particular T-sequence or determine that the particular T-sequence is not valid because of an error, etc. As a way to diminish the time and processing that would be required with a simple matching approach, a "Hashing function" has been used as a device to simplify bar code decoding. A Hashing function is a mathematical relationship that is used to combine all of components of a T-sequence with relative weightings to provide, as an output, a single number of one or more digits. The mathematical relationship may typically be determined on a trial and error basis, with the goal of choosing a relationship having the characteristic of converting each T-sequence into a unique output number. The results of use of such a Hashing function are illustrated in FIG. 3. Thus, with reference to the first row in FIG. 3, assume that the T-sequence shown, when each integer is multiplied by a particular weighting factor, the results added, and the aggregate divided by a constant (as provided by a hypothetical Hashing function) provides an output number "1" shown in the first column. The FIG. 3 table then cross-references the output number 1 to the first decoded value "0", shown in the last column.
Thus, a specific T-sequence is processed by use of the Hashing function to provide the output number 1 and the T-sequence shown in the adjoining column of the first row is then compared to the specific T-sequence. If the T-sequence that generated the output number is the same as the T-sequence from the table, the corresponding decoded value (0 in this example) is identified as the decoded value of the T-sequence. In this case, a unique decoded value for a specific bar/space pattern is identified by a unique output number arrived at by use of the Hashing function to process the T-sequence of the bar/space pattern.
However, as a practical matter, a Hashing function may typically provide a unique output number for only about 80 percent of the unique bar/space patterns of a bar code coding set. For the remaining cases the same output number is duplicated for two or more different T-sequences, when processed by the Hashing function. The table of FIG. 3 provides the function of a Hashing table to enable identification of the decoded value actually intended to correspond to each one of the two or more T-sequences which provide the same output number. Briefly, if the output number in the first column is derived from a T-sequence which does not match the T-sequence immediately to the right of the output number a match is not made and instead the pointer column value in that row identifies a different row to be used for a matching attempt. Thus, in the row wherein the number in the first column is the output number "5", the pointer column identifies row 3. If the particular T-sequence resulting in the output number 5 is not identical to the T-sequence included in the second column of this row, then that particular T-sequence is compared to the T-sequence at column 2 of row 3. If the T-sequence is identical, the proper decoded value of the T-sequence is "2", if not the T-sequence is compared for identity with the T-sequence shown at column 2 of row 2027 as identified in the pointer column. If identical, the output value for this particular T-sequence (and its bar/space pattern) is "1021" if again a match is not found, then the T-sequence is invalid. Invalidity can result from errors in reading the bar code, from damage to the bar code, from faulty printing of the bar code, etc. In this example the conclusion as to invalidity is reached because it is predetermined that only three valid T-sequences result in a Hashing function output number of "5" and only the corresponding number of relevant pointers is provided. While not actually shown in FIG. 3, it will be understood that a different T-sequence is entered in the second column in each row of the FIG. 3 table.
It can thus be appreciated that the Hashing function approach, while more efficient than a straight comparison approach, still requires a significant level of processing activity and time in order to identify decoded values.
As a separate consideration, in prior bar code decoding arrangements (as embodied in bar code reader units) the decoded values of bar/space patterns are typically directly converted into alphanumeric characters, for example, which are representative of the original information decoded into the bar code. Thus, the decoded value of bar/space pattern may be "15" and this may correspond to the letter "C", for example. On a basis which is predetermined and physically or by programming built into the bar code decoder, the bar/space pattern resulting in the decoded value "15" always results in a decoder output signal representative of the letter "C". If, for a particular application, it should later be desired to provide decoder output signals representative of Russian, Chinese or Greek characters, or words, phrases or symbols, for example, there is typically no way to change from an Arabic character set to a different output character set, absent a significant level of modification of the bar code reader.
Objects of the present invention, therefore, are to provide bar code decoding methods characterized by one or more of the following:
simplified decoding of bar/space patterns of bar codes; PA0 direct correspondence of a numerical value of a bar/space pattern to the decoded value, for most bar/space patterns; PA0 dynamic replaceability of output data character sets without decoder modification; and PA0 replacement or supplementation of output data character sets based upon instructions encoded in a bar code readable by a bar code reader.